#include <stdio.h>
#include <stdlib.h>
#include <memory.h>

typedef enum { false, true } bool;
typedef int ElemSet; /* 默认矩阵元素为整型 */
typedef struct MatrixNode *Matrix;
struct MatrixNode {
    ElemSet **t;
    int row;
    int col;
};
#define kMaxS 4 /* 解分量的值域规模|S|的上限 */

ElemSet **Create2DArray(int row, int col) {
    /* 动态声明row行col列的二维数组 */
    ElemSet *a, **t;
    int i;

    a = (ElemSet *)malloc(sizeof(ElemSet) * row * col);
    t = (ElemSet **)malloc(sizeof(ElemSet *) * row);
    for (i = 0; i < row; i++)
        t[i] = &a[col * i];
    return t;
}

void Free2DArray(ElemSet **t) {
    /* 释放二维数组空间 */
    free(t[0]);
    free(t);
}

bool Check(int s[], Matrix T, int i) {
    /* 仍然按分书问题的2个约束进行检查 */
    int n, j;
    bool ret;

    ret = true; /* 初始化返回值 */
    n = T->row; /* 解的分量数等于关系矩阵的行数 */
    for (j = 1; j < i; j++) { /* 检查每个解分量 */
        if (s[i - 1] == s[j - 1]) {
            ret = false; /* 不满足约束（1） */
            break;
        }
    }
    if (T->t[i - 1][s[i - 1] - 1] == 0) {
        ret = false; /* 不满足约束（2） */
    }
    return ret;
}

void Print(int *s, int n) {
    /* 输出一组解 */
    int i;

    printf("(%d", s[0]);
    for (i = 1; i < n; i++) {
        printf(", %d", s[i]);
    }
    printf(")\n");
}

/* 算法15-5：回溯法的通用伪代码 Backtracking (i, n) */
bool Backtracking(Matrix T, int *s, int i, int n) {
    /* 以下代码仅为示范模板                                   */
    /* 函数参数中除了必须的i和n，还需要传入特定问题的相关参数 */
    /* 以分书问题为例，还需要传入关系矩阵T和解向量s           */

    bool result;

    result = false;
    if (i > n) { /* 所有分量均已解决，成功结束 */
        Print(s, n);
        result = true;
    } else {
        /* 这里假设所有解分量的值域规模都是kMaxS */
        /* 数组下标从0开始，所以s的编号要减1 */
        for (s[i - 1] = 1; s[i - 1] <= kMaxS; s[i - 1]++) {
            if (Check(s, T, i) ==
                        true) { /* (s[1], ..., s[i])满足问题得解的约束条件 */
                result = Backtracking(T, s, i + 1, n); /* 继续深度优先搜索 */
                if (result == false) { /* S[i+1]中所有元素都不能构成部分解 */
                    /* 消除si的影响，回溯到(s[1], ..., s[i-1]) */
                }
            }
            if (result == true) { /* 找到了解 */
                break; /* 找到一组解就结束 */
                /* 若需要找到所有解，则不跳出 */
            }
        } /* 结束对S[i]中所有s[i]的检查*/
    }
    return result;
}
/* 算法15-5 结束 */

int main(void) {
    Matrix T;
    int *s; /* 解的状态分量 */
    int n_people, n_book, i, j;

    scanf("%d %d", &n_people, &n_book);
    T = (Matrix)malloc(sizeof(struct MatrixNode));
    T->row = n_people;
    T->col = n_book;
    T->t = Create2DArray(T->row, T->col);
    for (i = 0; i < n_people; i++) {
        for (j = 0; j < n_book; j++) {
            scanf("%d", &T->t[i][j]);
        }
    }
    s = (int *)malloc(sizeof(int) * T->row);
    Backtracking(T, s, 1, T->row);
    Free2DArray(T->t);
    free(T);

    return 0;
}